﻿#include "bucket.h"
#include<cstdlib>
#include<iostream>
using namespace std;
#define window 10000
#define eval_every 100000
// 公共参数
#define gnerate_num 1000000
#define digit_num 7

//合并函数，用于在相同size的bucket超过2时进行链表的合并
int merge(pbucket tail, int n) {
    pbucket p = tail;
    //count用于计算相同类型桶的数目
    int count = 0;
    while (p->timestamp != 0) {
        if (p->size == n) {
            count++;
            //相同类型桶的数量如果为3，则需要合并
            if (count == 3) {
                //链表结构为带头节点的双线链表尾插，合并方向为向后合并
                pbucket del = p->next;
                n *= 2;
                p->size = n;
                p->timestamp = del->timestamp;
                del->next->prev = del->prev;
                del->prev->next = del->next;
                free(del);
                merge(p, n);
                break;
            }
            else {
                p = p->prev;
            }
        }
        else {
            break;
        }
    }
    return 0;
}

//销毁双向链表
void destroy(pbucket head) {
    pbucket p = head->next;
    pbucket q = head->next;
    while (q != NULL) {
        q = p->next;
        free(p);
        p = q;
    }
}
//重载销毁函数，用于clip函数超出窗口的bucket
void destroy(pbucket head, pbucket end) {
    pbucket p = head->next;
    pbucket q = head->next;
    while (q != end) {
        q = p->next;
        free(p);
        p = q;
    }
    head->next = end;
    end->prev = head;
}

//修剪(销毁)超出window的bucket
void clip(int begin_time, pbucket head) {
    pbucket p = head->next;
    if (p->timestamp > begin_time) return;
    else {
        while (p->timestamp <= begin_time) {
            p = p->next;
        }
        destroy(head, p);
    }
}

//格式化输出链表结果
void show_result(int time, pbucket* head) {
    pbucket p;
    cout << "********************************" << endl;
    cout << "timestamp:" << time << endl;
    for (int i = 0; i < digit_num; i++) {
        p = head[i]->next;
        while (p) {
            cout << p->timestamp << "," << p->size << "->";
            p = p->next;
        }
        cout << "NULL" << endl;
    }
}

//使用DGIM根据bucket链表估算窗口内数据流总和
int calculate_DGIM(pbucket* h) {
    pbucket p;
    int sum = 0;
    int digit_sum;
    for (int i = 0; i < digit_num; i++) {
        digit_sum = 0;
        p = h[i]->next;
        digit_sum += (p->size) / 2;           //第一个bucket的size要除以2
        p = p->next;
        while (p) {
            digit_sum += p->size;
            p = p->next;
        }
        sum += digit_sum * pow(2, i);       //按位加和
    }
    return sum;
}